class MinHeap {
  constructor() {
    this.heap = [];
  }
  swap(i1, i2) {
    const temp = this.heap[i1];
    this.heap[i1] = this.heap[i2];
    this.heap[i2] = temp;
  }
  getParentIndex() {
    // return Math.floor((i - 1) / 2);
    return (i - 1) >> 1;
  }
  // 下移操作
  shiftUp(index) {
    if (index == 0) {
      return;
    }
    const parentIndex = this.getParentIndex(index);
    if (this.heap[parentIndex] > this.heap[index]) {
      this.swap(parentIndex, index);
      this.shiftUp(parentIndex);
    }
  }
  /** 插入
   * 1. 将值插入堆的底部，即数组的尾部
   * 2. 上移：将这个值和它的父节点进行交换，直到父节点小于等于这个插入的值
   * 3. 大小为k的堆中插入元素的时间复杂度为O(logk)
   */
  insert(value) {
    this.heap.push(value);
    this.shiftUp(this.heap.length - 1);
  }
  shiftDown(index) {}
  pop() {
    this.heap[0] = this.heap.pop();
    this.shiftDown();
  }
  /** 删除
   * 1. 用数组尾部元素替换堆顶
   * 2. 下移：将新堆顶和其子节点进行交换，直到子节点大于等于这个新堆顶
   * 3. 时间复杂度为O(logk)
   */
  delete() {}
}
